package now_coder.stack.ncs;

import java.util.Arrays;
import java.util.Stack;

public class NC157 {

    public int[][] foundMonotoneStack(int[] nums) {
        int[][] ans = new int[nums.length][2];

        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]){
                ans[stack.pop()][1] = i;
            }
            stack.push(i);
        }

        while (!stack.isEmpty())
            ans[stack.pop()][1] = -1;

        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]){
                ans[stack.pop()][0] = i;
            }
            stack.push(i);
        }

        while (!stack.isEmpty())
            ans[stack.pop()][0] = -1;

        return ans;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.deepToString(new NC157().foundMonotoneStack(new int[]{3, 4, 1, 5, 6, 2, 7})));
    }

}
